package org.jheuristics.ga.operators.selectors;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import org.jheuristics.Individual;
import org.jheuristics.ga.DefaultPopulation;
import org.jheuristics.ga.GAConfig;
import org.jheuristics.ga.GAStatus;
import org.jheuristics.ga.Population;
import org.jheuristics.ga.multiObjective.DistanceAlgorithm;

/**
 * TODO
 *
 * @author Marcell Manfrin, marcell@ourgrid.org, Oct 28, 2005
 */
public class GroupSelector extends AbstractDistanceSelector {

	/**
	 * TODO
	 *
	 * @param densityAlgorithm
	 */
	public GroupSelector(DistanceAlgorithm densityAlgorithm) {
		super(densityAlgorithm);
	}
	
	/* 
	 * 
	 * ESTA AQUI PELA QUESTAO DO LOG do AG
	 * (non-Javadoc)
	 * @see org.jheuristics.ga.operators.Selector#select(org.jheuristics.ga.Population, int, org.jheuristics.ga.GAStatus, org.jheuristics.ga.GAConfig)
	 */
	public Individual[] select(Population population, int howMany, GAStatus status, GAConfig config) {
		if (null == population) {
			throw new NullPointerException();
		}
		if (0 > howMany) {
			throw new IllegalArgumentException();
		}
		if (0 == howMany) {
			return new Individual[0];
		}
		if (population.size() <= howMany) {
			return population.toIndividualArray();
		}
		return select(population.toIndividualArray(), howMany, status, config);
	}

	/**
	 * TODO
	 *
	 * @param individuals
	 * @param howMany
	 * @param status
	 * @param config
	 * @return
	 * @see org.jheuristics.ga.operators.selectors.AbstractDistanceSelector#select(org.jheuristics.Individual[], int, org.jheuristics.ga.GAStatus, org.jheuristics.ga.GAConfig)
	 */
	protected Individual[] select(Individual[] individuals, int howMany, GAStatus status, GAConfig config) {
		List[] individualsDistances = getDistanceAlgorithm().getDistances(individuals, status, config);
		List clusters = new LinkedList();
		for (int i = 0; i < individuals.length; i++) {
			Set set = new TreeSet();
			set.add(new Integer(i));
			clusters.add(set);
		}
		while (clusters.size() > howMany) {
			List[] clustersDistances = getClusterDistances(clusters, individualsDistances);
			int mini = 0;
			int minj = 1;
			double min = ((Double) clustersDistances[0].get(0)).doubleValue();
			for (int i = 0; i < clustersDistances.length; i++) {
				for (int j = i; j < clustersDistances[i].size(); j++) {
					double value = ((Double) clustersDistances[i].get(j)).doubleValue();
					if (value < min) {
						mini = i;
						minj = j+1;
						min = value;
					}
				}
			}
			// grouping
			Set cluster1 = (Set) clusters.get(mini);
			Set cluster2 = (Set) clusters.get(minj);
			Set grouping = new TreeSet();
			grouping.addAll(cluster1);
			grouping.addAll(cluster2);
			clusters.remove(cluster1);
			clusters.remove(cluster2);
			clusters.add(grouping);
		}
		clusters = getClusterOfPopulation(clusters, individuals);
		Population result = new DefaultPopulation();
		for (Iterator it = clusters.iterator(); it.hasNext(); ) {
			Population population = (Population) it.next();
			if (population.size() > 1) {
				List[] distances = getDistanceAlgorithm().getDistances(population.toIndividualArray(), status, config);
				result.addIndividual(population.getIndividual(getMinimumAverageDistance(distances)));
			} else {
				result.addIndividuals(population);
			}
		}
		return result.toIndividualArray();
	}

	/**
	 * TODO
	 *
	 * @param clusters
	 * @param individualsDistances
	 * @return
	 */
	private List[] getClusterDistances(List clusters, List[] individualsDistances) {
		List[] distances = new List[clusters.size()];
		for (int i = 0; i < distances.length; i++) {
			distances[i] = new LinkedList();
		}
		for (int i = 0; i < distances.length; i++) {
			for (int j = i+1; j < distances.length; j++) {
				Set cluster1 = (Set) clusters.get(i);
				Set cluster2 = (Set) clusters.get(j);
				Double distance = new Double(getDistance(cluster1, cluster2, individualsDistances));
				distances[i].add(distance);
				distances[j].add(distance);
			}
		}
		return distances;
	}

	/**
	 * TODO
	 *
	 * @param cluster1
	 * @param cluster2
	 * @param individualsDistances
	 * @return
	 */
	private double getDistance(Set cluster1, Set cluster2, List[] individualsDistances) {
		double sum = 0.0;
		for (Iterator it1 = cluster1.iterator(); it1.hasNext(); ) {
			int index1 = ((Integer) it1.next()).intValue();
			for (Iterator it2 = cluster2.iterator(); it2.hasNext(); ) {
				int index2 = ((Integer) it2.next()).intValue();
				int i, j;
				if (index1 < index2) {
					i = index1;
					j = index2 - 1;
				} else {
					i = index2;
					j = index1 - 1;
				}
				sum += ((Double) individualsDistances[i].get(j)).doubleValue();
			}
		}
		return sum / (cluster1.size() * cluster2.size());
	}

	/**
	 * TODO
	 *
	 * @param clusters
	 * @param individuals
	 * @return
	 */
	private List getClusterOfPopulation(List clusters, Individual[] individuals) {
		List result = new LinkedList();
		for (Iterator it = clusters.iterator(); it.hasNext(); ) {
			Set cluster = (Set) it.next();
			Population population = new DefaultPopulation();
			for (Iterator it1 = cluster.iterator(); it1.hasNext(); ) {
				int index = ((Integer) it1.next()).intValue();
				population.addIndividual(individuals[index]);
			}
			result.add(population);
		}
		return result;
	}

	/**
	 * TODO
	 *
	 * @param distances
	 * @return
	 */
	private int getMinimumAverageDistance(List[] distances) {
		double[] average = new double[distances.length];
		for (int i = 0; i < average.length; i++) {
			average[i] = getAverage(distances[i]);
		}
		double min = average[0];
		int index = 0;
		for (int i = 1; i < average.length; i++) {
			if (average[i] < min) {
				min = average[i];
				index = i;
			}
		}
		return index;
	}

	/**
	 * TODO
	 *
	 * @param list
	 * @return
	 */
	private double getAverage(List list) {
		double value = 0.0;
		for (Iterator iter = list.iterator(); iter.hasNext();) {
			Double element = (Double) iter.next();
			value += element.doubleValue(); 
		}
		return value / list.size();
	}

}
